(number-theory-basics)=
# Basics

This page contains pre-university level elementary results in number theory.

## Definitions

:::{prf:definition} Divisibility

For all integers $a,b$, where $b\neq 0$, $b$ **divides** $a$ iff there exists an integer $n$ such that $a=nb$.
:::

:::{prf:definition} Prime Number

For all integers $n\geq 2$, $n$ is **prime** iff it has exactly $1$ and $n$ itself as its positive divisors.
:::

:::{prf:definition} Coprime Numbers

For all integers $p,q$, where $p,q\neq 0$,  
$p$ and $q$ are **coprime** iff their greatest common divisor $\gcd(p,q)$ is $1$.
:::

## Propositions

:::{prf:proposition}
:label: consecutive-coprime

For all prime numbers $p$, $p$ and $p+1$ are coprime.
:::

:::{prf:proof}

Take any common divisor $d$ of $p$ and $p+1$. By the property of divisibility, $d\mid p$ and $d\mid p+1$ implies that $d\mid (p+1)-p$ or $d\mid 1$. Since $d$ is a divisor of $1$, it must be $d=1$ only. Therefore, $p$ and $p+1$ are coprime.
:::

:::{prf:proof}

Take the greatest common divisor $d$ of $p$ and $p+1$.

Since $d\mid p$ and $p$ is prime, $d$ must be either $1$ or $p$:

* If $d=1$, then the only common divisor of $p$ and $p+1$ is $1$. Therefore, $p$ and $p+1$ are coprime.  
* If $d=p$, then $p\mid (p+1)$. This implies that $p+1=pn\iff p(n-1)=1$ for some integer $n$. However, this is impossible since $p$ is prime and thus greater than $1$.
:::

---

:::{prf:proposition}

For all prime numbers $p$ and integers $a\geq 2$, $p$ divides $a$ iff $p$ divides $a^2$.
:::

:::{prf:proof}

Take any prime numbers $p$ and integers $a\geq 2$.

To show $\implies$, assume $p\mid a$.  
Then there exists an integer $n$ such that $a=np$. This implies that $a^2=n^2p^2$, and thus $p\mid a^2$.

To show $\impliedby$, assume $p\mid a^2$.  
Assume for a contradiction that $p$ does not divide $a$, meaning $\gcd(p,a)=1$.  
By Bezout's identity ({prf:ref}`bezout-identity`), there exist integers $x,y$ such that $px+ay=\gcd(p,a)=1$. Multiply both sides to obtain $apx+a^2y=a$. Since $p$ divides the LHS, it must divide the RHS $a$, which is a contradiction.
:::

## Lemmas

:::{prf:lemma} Euclid's Division Lemma

For all integers $a,b$, where $b\neq 0$, there exist **unique** integers $q,r$ such that  
$a=bq+r$ and $0\leq r<|b|$.
:::

:::{prf:proof}

TODO
:::

## Theorems

:::{prf:theorem} Fundamental Theorem of Arithmetic
:label: fundamental-theorem-arithmetic

For all integers $n\geq 2$, there exists a unique prime factorization of $n$.
:::

:::{prf:proof}

TODO
:::

---

:::{prf:theorem} Bezout's Identity
:label: bezout-identity

For all integers $a,b$, there exist integers $x,y$ such that $ax+by=\gcd(a,b)$.
:::

:::{prf:proof}

Take any integers $a,b$. 

Consider the sequence of pairs $(r_i,r_{i+1})$ defined by the Euclidean algorithm,

* $r_{-2}=q_0\cdot r_{-1}+r_0$
* $r_{-1}=q_1\cdot r_0+r_1$
* $r_0=q_2\cdot r_1+r_2$
* ...
* $r_{n-2}=q_n\cdot r_{n-1}+r_n$

where $r_{-2}=a,r_{-1}=b$ and $r_n=0$.

The proof proceeds by the (reversed) mathematical induction.  
For each $i$, we assert that there exist integers $x,y$ such that $r_{i-2}\cdot x+r_{i-1}\cdot y=d$, where $d=\gcd(a,b)$.  
The claim of the theorem holds by letting $i=0$.

Base case $i=n$:  
Note that $r_{n-1}=d$ and $r_n=0$ by the correctness of the Euclidean algorithm.  
Hence we have that $r_{n-2}=q_n\cdot r_{n-1}+r_n\iff r_{n-2}-(q_n-1)\cdot r_{n-1}=d$,  
and thus there exist integers $x=1,y=1- q_n$ such that $r_{-2}\cdot x+r_{-1}\cdot y=d$.

Inductive step $i=k$:  
Assume by the inductive hypothesis there exist integers $s,t$ such that $r_{k-2}\cdot s+r_{k-1}\cdot t=d$.  
Note that $r_{k-3}=q_{k-1}\cdot r_{k-2}+r_{k-1}$ and $r_{k-1}\cdot t=d-r_{k-2}\cdot s$.  
Hence we have $r_{k-3}=q_{k-1}\cdot r_{k-2}+(d-r_{k-2}\cdot s)/t$.  

By elementary algebra we obtain:

$$
\begin{align}
& r_{k-3}=q_{k-1}\cdot r_{k-2}+(d-r_{k-2}\cdot s)/t \\
\iff\quad& r_{k-3}\cdot t=q_{k-1}\cdot r_{k-2}\cdot t+d-r_{k-2}\cdot s \\
\iff\quad& r_{k-3}\cdot t-r_{k-2}(q_{k-1}\cdot t-s)=d
\end{align}
$$

Hence there exist $x=t,y=s-q_{k-1}\cdot t$ such that $r_{k-3}\cdot x+r_{k-2}\cdot y=d$.
:::